package main

func isInterleave(s1 string, s2 string, s3 string) bool {
	if len(s1)+len(s2) != len(s3) {
		return false
	}
	dp := make([][]bool, len(s1)+1)
	for i := range dp {
		dp[i] = make([]bool, len(s2)+1)
		for j := range dp[i] {
			if i == 0 && j == 0 {
				dp[i][j] = true
			} else if i == 0 {
				if dp[i][j-1] && s2[j-1] == s3[j-1] {
					dp[i][j] = true
				}
			} else if j == 0 {
				if dp[i-1][j] && s1[i-1] == s3[i-1] {
					dp[i][j] = true
				}
			} else {
				if dp[i][j-1] && s2[j-1] == s3[j-1+i] {
					dp[i][j] = true
				}
				if dp[i-1][j] && s1[i-1] == s3[i-1+j] {
					dp[i][j] = true
				}
			}
		}
	}
	return dp[len(s1)][len(s2)]
}

func main() {
	println(isInterleave("aa", "db", "aadb"))
}
